算法概论(DPV)第2章分治算法总结

书籍介绍：

https://book.douban.com/subject/3155710/

配套课程：

CS170（伯克利），CS161（斯坦福）

github仓库：

https://github.com/Doraemonzzz/Algorithm-DPV

备注：图片来自于电子书中。

之前只回顾了课程习题，后续也会回顾每章重点内容，部分已经整理过的部分会给出链接，这次回顾第2章——分治算法。

第2章——分治算法

主定理

如果

$T(n) \le aT\left(\frac n b \right) + O(n^d)$

那么

$T(n)=\begin{cases} O(n^d), &a<b^d\\ O(n^d\log n), &a=b^d\\ O(n^{\log_b a }), & a>b^d \end{cases}$

笔记：

https://doraemonzzz.com/2018/09/21/%E6%96%AF%E5%9D%A6%E7%A6%8F%E7%AE%97%E6%B3%95%E4%B8%93%E9%A1%B9%E8%AF%BE%E7%A8%8BCourse1%20week2%E5%86%85%E5%AE%B9%E5%9B%9E%E9%A1%BE/#toc-heading-5

乘法（Karatsuba Multiplication）

时间复杂度：

$\begin{aligned} T(n)&=3 T(n / 2)+O(n)\\ T(n)&= O(n^{\log_2 3}) \end{aligned}$

笔记：

https://doraemonzzz.com/2018/09/09/%E6%96%AF%E5%9D%A6%E7%A6%8F%E7%AE%97%E6%B3%95%E4%B8%93%E9%A1%B9%E8%AF%BE%E7%A8%8BCourse1%20week1%E5%86%85%E5%AE%B9%E5%9B%9E%E9%A1%BE/#toc-heading-2

归并排序

merge函数：

递归版本：

迭代版本：

$Q$是队列，eject从队列头部弹出元素，inject向队列尾部插入元素。

时间复杂度：

$\begin{aligned} T(n)&=2 T(n / 2)+O(n)\\ T(n)&= O(n \log n) \end{aligned}$

寻找中项

笔记：

https://doraemonzzz.com/2018/10/01/%E6%96%AF%E5%9D%A6%E7%A6%8F%E7%AE%97%E6%B3%95%E4%B8%93%E9%A1%B9%E8%AF%BE%E7%A8%8BCourse1%20week4%E5%86%85%E5%AE%B9%E5%9B%9E%E9%A1%BE/#toc-heading-2

（个人感觉这部分笔记比课本讲的更加详细）

矩阵乘法

笔记：

https://doraemonzzz.com/2018/09/21/%E6%96%AF%E5%9D%A6%E7%A6%8F%E7%AE%97%E6%B3%95%E4%B8%93%E9%A1%B9%E8%AF%BE%E7%A8%8BCourse1%20week2%E5%86%85%E5%AE%B9%E5%9B%9E%E9%A1%BE/#toc-heading-4

快速傅里叶变换（FFT）

普通视角

$d$次多项式可以用$d+1$个系数或者$d+1$个值表示：

计算：系数表示法$\rightarrow$值表示法
插值：值表示法$\rightarrow$系数表示法

基于值表示法的多项式乘法如下：

整个过程如下：

根据系数计算值
计算值乘积
恢复系数

FFT的核心是下式：

$A(x)=A_{e}\left(x^{2}\right)+x A_{o}\left(x^{2}\right)$

由此得到如下算法：

其中$w$是$1$的$n$次根。

时间复杂度：

$\begin{aligned} T(n)&=2 T(n / 2)+O(n)\\ T(n)&= O(n \log n) \end{aligned}$

FFT实现了系数到值的快速计算，即

$\langle\text { values }\rangle=\text { FFT }(\langle\text { coefficients }\rangle, \omega)$

根据之前的介绍，我们还需要值到系数的计算，那么是否存在快速的计算方法呢？事实上，我们有

$\langle\text { coefficients }\rangle=\frac{1}{n} \text { FFT }(\langle\text { values }\rangle, \omega^{-1})$

这点从矩阵视角更容易解释。

矩阵视角

值和系数的对应关系为：

$\left[\begin{array}{c} A\left(x_{0}\right) \\ A\left(x_{1}\right) \\ \vdots \\ A\left(x_{n-1}\right) \end{array}\right]=\left[\begin{array}{ccccc} 1 & x_{0} & x_{0}^{2} & \cdots & x_{0}^{n-1} \\ 1 & x_{1} & x_{1}^{2} & \cdots & x_{1}^{n-1} \\ & & \vdots & & \\ 1 & x_{n-1} & x_{n-1}^{2} & \cdots & x_{n-1}^{n-1} \end{array}\right]\left[\begin{array}{c} a_{0} \\ a_{1} \\ \vdots \\ a_{n-1} \end{array}\right]$

FFT对应的矩阵为：

$M_{n}(\omega)=\left[\begin{array}{ccccc} 1 & 1 & 1 & \cdots & 1 \\ 1 & \omega & \omega^{2} & \cdots & \omega^{n-1} \\ 1 & \omega^{2} & \omega^{4} & \cdots & \omega^{2(n-1)} \\ & & \vdots & & \\ 1 & \omega^{j} & \omega^{2 j} & \cdots & \omega^{(n-1) j} \\ & & \vdots & & \\ 1 & \omega^{(n-1)} & \omega^{2(n-1)} & \cdots & \omega^{(n-1)(n-1)} \end{array}\right]$

所以FFT可以表示为矩阵形式：

$\left[\begin{array}{c} A\left(x_{0}\right) \\ A\left(x_{1}\right) \\ \vdots \\ A\left(x_{n-1}\right) \end{array}\right]=M_{n}(\omega)\left[\begin{array}{c} a_{0} \\ a_{1} \\ \vdots \\ a_{n-1} \end{array}\right]$

利用线代的知识可得：

$M_{n}(\omega)^{-1}=\frac{1}{n} M_{n}\left(\omega^{-1}\right)$

所以

$\left[\begin{array}{c} a_{0} \\ a_{1} \\ \vdots \\ a_{n-1} \end{array}\right]=M_{n}(\omega)^{-1}\left[\begin{array}{c} A\left(x_{0}\right) \\ A\left(x_{1}\right) \\ \vdots \\ A\left(x_{n-1}\right) \end{array}\right] =\frac{1}{n} M_{n}\left(\omega^{-1}\right)\left[\begin{array}{c} A\left(x_{0}\right) \\ A\left(x_{1}\right) \\ \vdots \\ A\left(x_{n-1}\right) \end{array}\right]$

FFT的矩阵解释

最后从矩阵乘法的角度解释FFT：

第一步，对矩阵的列重新排列，将偶数下标放在前$n/2$列，奇数下标放在后$n/2$列。

第二步，以$n/2$为分界线，考虑第$j$行的元素。

前$n/2$行，偶数下标：

$\omega^{j 2k}=\omega^{2j k}=(w^2)^{jk}$

前$n/2$行，奇数下标：

$\omega^{j (2k+1)} = w^j. \omega^{2j k}= w^j.(w^2)^{jk}$

后$n/2$行，偶数下标：

$\omega^{(j+ n/2) 2k} =\omega^{2j k} \omega^{kn}=\omega^{2j k} =(w^2)^{jk}$

后$n/2$行，奇数下标：

$\omega^{(j+ n/2) (2k+1)} =\omega^{2j k} \omega^{kn}w^j w^{n/2}=-w^j .\omega^{2j k} =- w^j.(w^2)^{jk}$

所以四个子矩阵都可以根据$M_{n / 2}\left(\omega^{2}\right)$计算。

整体如下：

完整算法：

电路视角

电路视角见课本。